package org.example.dynamic_planning;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Multiple_backpack {
    public static void main(String[] args) {
        //多重背包

        //你是一名宇航员，即将前往一个遥远的行星。在这个行星上，有许多不同类型的矿石资源，每种矿石都有不同的重要性和价值。你需要选择哪些矿石带回地球，但你的宇航舱有一定的容量限制。
        //给定一个宇航舱，最大容量为 C。现在有 N 种不同类型的矿石，每种矿石有一个重量 w[i]，一个价值 v[i]，以及最多 k[i] 个可用。不同类型的矿石在地球上的市场价值不同。你需要计算如何在不超过宇航舱容量的情况下，最大化你所能获取的总价值。
        //输入描述
        //输入共包括四行，第一行包含两个整数 C 和 N，分别表示宇航舱的容量和矿石的种类数量。
        //接下来的三行，每行包含 N 个正整数。具体如下：
        //第二行包含 N 个整数，表示 N 种矿石的重量。
        //第三行包含 N 个整数，表示 N 种矿石的价格。
        //第四行包含 N 个整数，表示 N 种矿石的可用数量上限。
        //输出描述
        //输出一个整数，代表获取的最大价值。
        //输入示例
        //10 3
        //1 3 4
        //15 20 30
        //2 3 2
        //输出示例
        //90
        Scanner sc = new Scanner(System.in);
        int v = sc.nextInt();
        int n = sc.nextInt();
        ArrayList<Integer> weight = new ArrayList<>();
        ArrayList<Integer> value = new ArrayList<>();
        ArrayList<Integer> nums = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int w = sc.nextInt();
            weight.add(w);
        }
        for (int i = 0; i < n; i++) {
            int va = sc.nextInt();
            value.add(va);
        }
        for (int i = 0; i < n; i++) {
            int num = sc.nextInt();
            nums.add(num);
        }
        for (int i = 0; i < nums.size(); i++) {
            if (nums.get(i) == 1) continue;
            for (int j = 1; j < nums.get(i); j++) {
                weight.add(weight.get(i));
                value.add(value.get(i));
            }
        }
        int[] dp = new int[v + 1];
        for (int i = 0; i < weight.size(); i++) {
            for (int j = v; j >= weight.get(i); j--) {
                dp[j] = Math.max(dp[j],dp[j-weight.get(i)]+value.get(i));
            }
        }
        System.out.println(dp[v]);
    }
}
